package 十大排序算法;

public class 插入排序 {
    /**
     * public static void insertionSort(int[] arr){
     *         for (int i = 1; i < arr.length; i++) {
     *             int insert = arr[i];
     *             for (int j = i-1; j >=0 && arr[j]>insert; j--) {
     *                     arr[j+1] = arr[j];
     *                 //哦哦哦这里你要考虑到j是会变小的 退出上个循环的情况下 他是刚好j+1刚好是对应那个空缺的地方
     *                 arr[j+1] = insert;
     *             }
     *         }
     *     }
     *
     */
    public void sort(int arr[]){
        for (int i = 1; i < arr.length; i++) {
            //要插入的数
            int insertVal = arr[i];
            //被插入的数 (和前一位数比较)
            int index = i-1;
            while (index>=0&&insertVal<arr[index]){
                //把arr[index]向后移动
                arr[index+1] = arr[index];
                //index向前移动
                index--;
            }
            //while结束后就是找到指定位置了 然后把插入数放在合适位置上
            arr[index+1] = insertVal;
        }
    }

}
